package com.bjpowernode.javase.array;
/*
    二分查找数组下标
        1、二分法算法是基于排序的基础上完成的
        2、arr = {4(下标0), 5 , 12 , 48, 89, 85, 99 ,158, 225, 610, 928(下标10)};
            通过二分法找610
                (0 + 10) / 2 = 5
                arr[5] = 85 < 610
                说明被查找的元素在右边，故开始下标变成5 + 1 = 6，结束坐标不变
                (6 + 10) / 2 = 8
                arr[8] = 225 < 610
                说明被查找的元素在右边，故开始下标变成8 + 1 = 9，结束坐标不变
                (6 + 10) / 2 = 9
                arr[9] = 610
                查找成功
        3、若被查找的元素在左边，则开始元素下标不变，结束坐标+1
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {4, 5 , 12 , 48, 89, 85, 99 ,158, 225, 610, 928};

        //找出610这个元素的下标
        int index = binarySearch(arr , 928);
        System.out.println(index == -1 ? "该元素不存在" : "该元素的下标是" + index);
    }

    public static int binarySearch(int[] arr, int i) {
        //开始下标
        int begin = 0;
        //结束下标
        int end = arr.length - 1;
        while (begin <= end){
            //中间元素下标
            int mid = (begin + end) / 2;
            if(arr[mid] == i){
                return mid;
            }else if(arr[mid] < i){
                //目标元素下标在开始元素下标的右边，开始元素下标需要重新赋值
                begin = mid +1;
            }else{
                //目标元素下标在开始元素下标的左边，结束元素下标需要重新赋值
                end = mid - 1;
            }
        }
        return -1;
    }

}
